/**
复原IP地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，
但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，***返回所有可能的有效 IP 地址***，
这些地址可以通过在 s 中插入 '.' 来形成。
你 **不能** 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
 */

/**
 * 【终止条件】 
 * 1. k=4
 * 2. 每个元素都在 0-255； 0不能做前导
 * 3. 所有元素都选择/分割
 */
var restoreIpAddresses = function(s) {
  const res = [];
  const path = [];
  const k = 4;
  const isVaild = (str) => {
    if(Number(str)>255 || (str.length>1 && str[0]=='0')) return false;
    return true
  }
  const backTrack = (index) => {
    if(path.length == k && index >= s.length) {
      res.push(path.join('.'));
      return;
    }
    for(let i=index; i<s.length; i++) {
      const str = s.slice(index,i+1);
      if(isVaild(str)) {
        path.push(str);
        backTrack(i+1);
        path.pop();
      }else {
        continue;
      }
    }
  }
  backTrack(0);
  return res;
};
const s = "25525511135";
console.log('复原IP地址', restoreIpAddresses(s));
